package 哈希表;

import java.util.HashSet;

/**
 * @Author Weton Li
 * @Date 2021/3/16 16:01
 */
public class 八_求最长连续序列 {

    public static int longestConsuctiveSequence(int[] nums) {

        int maxLength = 0;
        HashSet<Integer> hashSet = new HashSet<>();

        for (int num : nums) {
            hashSet.add(num);
        }

        for (int i = 0; i < nums.length; i++) {

            int currNum = nums[i];
            // 从第一个数开始寻找连续的下一个数，如果找到，当前长度加一，使当前最大长度暂时变为当前长度
            int currLength = 1;

            if (!hashSet.contains(currNum - 1)) {
                while (hashSet.contains(currNum + 1)) { // 当不包含当前数时，遍历数组第二个数，再进行是否包含判断判断
                    currLength++; // 当前数本身长度为1，如果当前数+1包含在数组内，则长度再+1
                    currNum++; // 如果2包含在数组中，则当前数仍为1需要加1，再判断3是否包含在数组中
                }
            }

            if (currLength > maxLength) {
                maxLength = currLength;
            }
        }

        return maxLength;
    }

    /*
    private static boolean contains(int currNum, int[] nums) {

        for (int num : nums) {
            if (num == currNum) { // 如果 遍历出的一个数字等于当前数
                return true; // 当前数即在当前数组中
            }
        }
        return false;

    }*/


    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(longestConsuctiveSequence(nums)); // 4
    }
}
